1. Field of Invention
This invention relates generally to data modeling and analysis and more particularly to a computerized system for developing and using Bayesian belief networks, such as in data modeling and analysis.
2. Discussion of Related Art
Computerized data models are important in solving real-world problems because these models can predict future data and/or explain past data, especially for large and complex data sets where humans are unable to effectively understand the data. One data modeling technique is probabilistic modeling. Probabilistic modeling provides mathematically rigorous methods for handling uncertainty when modeling a problem domain and has an extremely wide range of applications, including medical diagnosis, bioinformatics, computer vision, signal processing, control systems, cognitive science, and financial modeling.
One technique with which probabilistic data may be modeled is Bayesian Networks (BN), also known as belief networks, Bayesian belief networks, probabilistic networks, or directed graphical models. Bayesian Networks are described in the literature such as Russell, P. & Norvig, P. (2003), Artificial Intelligence: A Modern Approach, (Second Edition) Upper Saddle River, N.J.: Prentice Hall; Jensen, F. V. (2001) Bayesian Networks and Decision Graphs, New York: Spring Verlag; and Pearl, J. (1988), Probabilistic Reasoning in Intelligent Systems: Networks of plausible Inference, San Mateo, Calif.: Morgan Kaufmann; which are hereby incorporated by reference. A BN consists of nodes connected by directed edges. Each node represents a particular random variable having some number of states. Both discrete nodes, which have a finite number of states, and continuous nodes, which have an infinite number of states, can exist in a BN. Each edge is directed from a parent node to a child node and represents the causal influence of the parent node on the child node.
Each node in a BN has a conditional probability distribution (CPD) associated with it that describes the causal influences of its parents. A CPD includes the probability of the node's variable being in a particular state as a function of the states of its parent nodes. There are no restrictions on the types of conditional probability distributions used and each node in the BN can use a different CPD. The CPD for node Child that has n parent nodes Parent1, Parent2, . . . , Parentn is represented by P(Child|Parent1, Parent2, . . . , Parentn), which specifies the conditional probability distribution for Child given the values of all the parent variables.
Bayesian networks are used to compute the probabilities that certain events will occur given the likelihood that certain other events have already occurred. These probabilities are called beliefs and are stated mathematically as P(X|e), or the probability of X given some evidence e. The beliefs for the nodes in the BN are calculated using the CPDs and the evidence.
The BN may be represented by data stored in a computer allowing automated data processing to compute beliefs. An inference engine (IE) is typically used to compute beliefs. Many different IE's are described in the literature, including Darwiche, A. (2003), A Differential Approach to Inference in Bayesian Networks, Journal of the ACM, 50(3), 280-305; Jensen, F. V. (2001), Bayesian Networks and Decision Graphs, New York: Spring Verlag; Dechter, R. (1999), Bucket Elimination: A Unifying Framework for Reasoning, Artificial Intellegence, 11341-85; Madsen, A. L. & Jensen, F. V. (1999), Lazy Propagation: A Junction Tree Algorithm based on Lazy Evaluation, Artificial Intellegence, 113(1-2), 203-245; Huang, C. & Darwiche, A. (1996), Inference in Belief Networks: A Procedural Guide, International Journal of Approximate Reasoning, 15225-263; Zhang, N. L. & Poole, D. (1994), A Simple Approach to Bayesian Network Computations, Proceedings of the 10th Canadian Conference on Artificial Intelligence, (pp. 171-178), Banff, Alberta; Shacter, R. D., D'Amrosio, B., & Del Favero, B. A. (1990), Symbolic Probabilistic Inference in Belief Networks, Proceedings of the 8th Nat'l Conference on Artificial Intelligence (AAAI-90), (pp. 126-131), Boston: MIT Press; Shafer, G. R. & Shenoy, P. P. (1990), Probability Propagation, Ann. Math. Artificial Intelligence; 2327-352; Lauritzen, S. L. & Spiegelhalter, D. J. (1988), Local Computation with Probabilities on Graphical Structures and Their Applications to Expert Systems, Journal of the Royal Statistical Society B, 50(2), and the above-mentioned Jensen, 2001 article and the Pearl, 1988 article, referenced above, all of which are hereby incorporated by reference. Often, an IE is built from a particular BN and can then be used to compute beliefs using any evidence. In other words, the CPDs and evidence are inputs to the IE and beliefs are the outputs. But only the evidence can change at run-time; if the CPD of any node in the BN changes in any way, the IE must be built again before beliefs can be calculated again.
The evidence e specifies the events that have already occurred. More specifically, the evidence provides a real number between zero and one (inclusive) for each state of each node that represents an event that has already occurred. These numbers represent the independent likelihood of the states for each observed node. So, in a typical BN, observations are obtained for some variables in the BN, and then beliefs are calculated for other nodes. Either a human operator or a computer then uses these beliefs to make decisions.
The process of receiving user input and computing beliefs is often performed by a software application program that has a user interface through which a user can provide inputs or obtain outputs. In the terminology of user interface development for computer software applications, a mode is defined as a set of functionality and interactions available to the user. In an application with only a single mode (also called modeless), any desired functionality and interactions can be available to the user. In an application with multiple modes (also called modal), the application is in one of the modes at any given time and there are certain functionality and interactions from the other modes that are not available to the user. To obtain access to the unavailable functionality and interactions, the user must explicitly switch the application into the appropriate mode using a mode-switching interaction.
User interface modes can be manifested in many different ways in a software application. Two common realizations of modes, especially related to Bayesian network development software, are modal dialogs and application modes. The first type, modal dialogs, are windows that are displayed over the main application window and accept input from the user. While the modal dialog is open, the user is prevented from interacting with any part of the application except for the modal dialog. The only way for the user to interact with any other part of the application is to close the modal dialog. Modal dialogs commonly contain “OK”, “Cancel”, and/or “Close” buttons that can be used to close the modal dialog and allow the user to once again interact with other windows in the application. (Note: other button names representing the action provided by the modal dialog can also close the dialog window, e.g., “Print”, “Update”, “Apply”, “Next” or “Finish”).
The second type of modes, application modes, are not as readily apparent to the user as modal dialogs. The application is initially in one mode that provides the user with some set of functionality and information displays, and some specific interaction switches the application to another mode with a different set of functionality and displays. This mode-switching interaction can be the click of a button, selection of a different tab, etc. To gain access to unavailable functionality or displays the user must explicitly perform the mode-switching interaction to switch the application to the desired mode and will lose access to the functionality and displays of the previous mode.
The major drawbacks of modal software applications are the disruption and delay caused by mode-switching interactions and the lack of availability of needed functionality and interactions not designed to be available across application modes. Users of poorly designed modal applications have complained that having to explicitly switch to a different mode is annoying because it requires focusing on the mode-switching interaction instead of on their main task and can require any number of tasks on the user's part to switch the mode. The ability of the users to use the software application is also impeded by not having access to desired functionality or interactions when needed, and subsequently forcing the user to move focus to identifying and selecting the required mode.
All current software applications for developing Bayesian networks are modal in some way. The most common is the application mode type, where two separate modes are provided, one for modifying the BN and one for using the BN (i.e., viewing beliefs as a function of a priori information and current evidence and/or providing additional evidence). In the first mode, functionality and interactions for modifying the BN are available to the user but functionality and interactions for using the BN are unavailable. Likewise, in the second mode, functionality and interactions for using the BN are available to the user but functionality and interactions for modifying the BN are unavailable. Typically, the user must explicitly click a button to switch modes.
More recent BN development software applications have improved with respect to this problem, but all current applications still have modal user interfaces. Instead of relying on two separate modes for modifying and using the BN, they provide much of the functionality and interactions in modal dialogs. In one application, interactions for adding and removing nodes and edges as well as posting and retracting evidence are always available in the main application window, but the user must open a modal dialog to add, remove, reorder, or rename the states of a node or to modify the CPD of a node. While the modal dialog is open the user is prevented from performing the interactions in the rest of the application. The user must explicitly close the modal dialog to receive access to these interactions again. Once the modal dialog is closed the user is again prevented from performing the interactions available in the modal dialog.